class Solution
{
private:
    unordered_map<long long, int> m;
    int ans = 0;

    void dfs(TreeNode* now, int tar, long long sum)
    {
        sum += now->val;
        long long tmp = sum - tar;

        if (m[tmp] > 0)
            ans += m[tmp];

        m[sum] += 1;

        if (now->left) dfs(now->left, tar, sum);
        if (now->right) dfs(now->right, tar, sum);

        m[sum] -= 1;
    }

public:
    int pathSum(TreeNode* root, int targetSum)
    {
        m[0] = 1;
        if (root == NULL) return 0;
        dfs(root, targetSum, 0);
        return ans;
    }
};